#ifndef TRIE_H_
#define TRIE_H_

#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <string>
#include <unordered_set>
#include <vector>

namespace lxj
{
//'0'~'9'=>0~9, '-'=>10, '#'=>11
class Trie {
    constexpr static int MAXN     = 2000001;
    inline static int (*tree)[12] = new int[MAXN][12]{0};
    inline static int* pass       = new int[MAXN]{0};
    inline static int* end        = new int[MAXN]{0};
    inline static int  cnt        = 0;

    Trie(const std::string& sequence)
    {
        if (sequence.empty()) return;
        std::string number;
        for (size_t i = 0; i < sequence.size(); i++) {
            if (sequence[i] == '#') {
                number += sequence[i];
                insert(number);
                number = "";
            }
            else {
                number += sequence[i];
            }
        }
    }

    inline int path(char c) { return (c >= '0' && c <= '9') ? c - '0' : (c == '#' ? 11 : 10); }

public:
    Trie(const Trie&) = delete;

    inline static Trie& instance(const std::string& sequence)
    {
        cnt = 1;
        static Trie trie(sequence);
        return trie;
    }

    inline void insert_sequence(const std::string& sequence)
    {
        std::string number;
        for (size_t i = 0; i < sequence.size(); i++) {
            if (sequence[i] == '#') {
                number += sequence[i];
                insert(number);
                number = "";
            }
            else {
                number += sequence[i];
            }
        }
    }

    inline void insert(const std::string& number)
    {
        if (number.empty()) return;

        int cur = 1;
        pass[cur]++;
        for (int i = 0, path; i < number.size(); i++) {
            path = this->path(number[i]);
            if (tree[cur][path] == 0) tree[cur][path] = ++cnt;
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur]++;
    }

    inline int count(const std::string& prefix)
    {
        int cur = 1;
        for (int i = 0, path; i < prefix.size(); i++) {
            path = this->path(prefix[i]);
            if (tree[cur][path] == 0) return 0;
            cur = tree[cur][path];
        }
        return pass[cur];
    }

    inline void clear()
    {
        for (int i = 0; i < cnt; i++) {
            std::fill(&tree[i][0], &tree[i][12], 0);
            pass[i] = 0;
            end[i]  = 0;
        }
    }
};

// 牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份
// 密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：
// 密匙 b 的长度不超过密匙 a 的长度。
// 对于任意 0 <= i < length(b)，有b[i+1] - b[i] == a[i+1] - a[i]
// 现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组
// 请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙
// 数组 a 和数组 b 中的元素个数均不超过 10^5
// 1 <= m, n <= 1000
// 测试链接 : https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932
inline std::vector<int> countConsistentKeys(
    int** a, int a_row, int a_col, int** b, int b_row, int b_col)
{
    auto& trie = Trie::instance("");
    for (int i = 0; i < a_row; i++) {
        std::string sequence;
        for (int j = 1; j < a_col; j++) {
            sequence += a[i][j] - a[i][j - 1] + '#';
        }
        trie.insert_sequence(sequence);
        sequence = "";
    }

    std::vector<int> ans;
    for (int i = 0; i < b_row; i++) {
        std::string cur;
        for (int j = 1; j < b_col; j++) {
            cur += b[i][j] - b[i][j - 1] + '#';
            ans.push_back(trie.count(cur));
            cur = "";
        }
    }
    trie.clear();
    return ans;
}

// 数组中两个数的最大异或值
// 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n
// 1 <= nums.length <= 2 * 10^5
// 0 <= nums[i] <= 2^31 - 1
// 测试链接 : https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
class TwoNumberMaxXor {
    inline static int MAX        = 3000001;
    inline static int (*tree)[2] = new int[MAX][2]{0};
    inline static int cnt        = 0;
    inline static int high       = 0;

public:
    TwoNumberMaxXor(int* arr, int len)
    {
        cnt     = 1;
        int max = 1 << 31;
        for (int i = 0; i < len; i++) {
            max = max > arr[i] ? max : arr[i];
        }
        for (int i = 0, pos; i < 31; i++) {
            pos = 1 << (30 - i);
            if ((pos & max) != 0) {
                high = 31 - i;
                break;
            }
        }

        for (int i = 0; i < len; i++) {
            insert(arr[i]);
        }
    }

    ~TwoNumberMaxXor()
    {
        for (int i = 1; i <= cnt; i++) {
            tree[i][0] = 0;
            tree[i][1] = 0;
        }
    }

    inline void insert(int num)
    {
        int cur = 1;
        for (int i = high, path; i >= 0; i--) {
            path            = (num >> i) & 1;
            tree[cur][path] = tree[cur][path] == 0 ? ++cnt : tree[cur][path];
            cur             = tree[cur][path];
        }
    }

    inline int max_xor(int num) const
    {
        int ans = 0;
        int cur = 1;
        for (int i = high, status, want; i >= 0; i--) {
            status = (num >> i) & 1;
            want   = status ^ 1;
            if (tree[cur][want] == 0) want ^= 1;
            ans |= (status ^ want) << i;
            cur = tree[cur][want];
        }
        return ans;
    }
};

// 前缀树的做法
// 好想
inline int find_max_xor(int* arr, int len)
{
    int             ans = 0;
    TwoNumberMaxXor mx(arr, len);
    for (int i = 0; i < len; i++) {
        int k = mx.max_xor(arr[i]);
        ans   = ans > k ? ans : k;
    }
    return ans;
}

// 用哈希表的做法
// 难想
inline int find_max_xor2(int* arr, int len)
{
    int max = 1 << 31;
    for (int i = 0; i < len; i++) {
        max = max > arr[i] ? max : arr[i];
    }

    int                     ans = 0;
    std::unordered_set<int> set;
    int                     high = 0;
    for (int i = 30, pos; i >= 0; i--) {
        pos = 1 << i;
        if ((pos & max) != 0) {
            high = i;
            break;
        }
    }

    for (int i = high; i >= 0; i--) {
        int better = ans | (1 << i);
        set.clear();
        for (int j = 0; j < len; j++) {
            int num = arr[j];
            num     = (num >> i) << i;
            set.insert(num);
            if (set.count(better ^ num) != 0) {
                ans = better;
                break;
            }
        }
    }
    return ans;
}

// 在二维字符数组中搜索可能的单词
// 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words
// 返回所有二维网格上的单词。单词必须按照字母顺序，通过 相邻的单元格 内的字母构成
// 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
// 同一个单元格内的字母在一个单词中不允许被重复使用
// 1 <= m, n <= 12
// 1 <= words.length <= 3 * 10^4
// 1 <= words[i].length <= 10
// 测试链接 : https://leetcode.cn/problems/word-search-ii/
class WordSearchII {
    inline constexpr static int MAX = 10001;
    inline static int (*tree)[26]   = new int[MAX][26]{0};
    inline static int*         pass = new int[MAX]{0};
    inline static std::string* end  = new std::string[MAX];
    inline static int          cnt  = 0;

public:
    inline void build(std::vector<std::string>& words)
    {
        cnt = 1;
        for (auto& word : words) {
            int cur = 1;
            pass[cur]++;
            for (int i = 0, path; i < word.size(); i++) {
                path = word[i] - 'a';
                if (tree[cur][path] == 0) tree[cur][path] = ++cnt;
                cur = tree[cur][path];
                pass[cur]++;
            }
            end[cur] = word;
        }
    }

    inline void clear()
    {
        for (int i = 1; i <= cnt; i++) {
            std::fill(&tree[i][0], &tree[i][26], 0);
            pass[i] = 0;
            end[i]  = "";
        }
    }

    inline std::vector<std::vector<int>> clone(std::vector<std::string>& words)
    {
        build(words);
        clear();
        std::vector<std::vector<int>> ans(MAX, std::vector<int>(26));
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < 26; j++) {
                ans[i][j] = tree[i][j];
            }
        }
        return ans;
    }

    inline std::vector<std::string> findWords(std::vector<std::vector<char>>& board,
                                              std::vector<std::string>&       words)
    {
        build(words);
        std::vector<std::string> ans;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, 1, ans);
            }
        }
        clear();
        return ans;
    }

    // board : 二维网格
    // i,j : 此时来到的格子位置，i行、j列
    // t : 前缀树的编号
    // List<String> ans : 收集到了哪些字符串，都放入ans
    // 返回值 : 收集到了几个字符串
    inline int dfs(
        std::vector<std::vector<char>>& board, int i, int j, int t, std::vector<std::string>& ans)
    {
        if (i < 0 || i == board.size() || j < 0 || j == board[0].size() || board[i][j] == 0)
            return 0;
        char tmp  = board[i][j];
        int  road = tmp - 'a';
        t         = tree[t][road];
        if (pass[t] == 0) return 0;
        int fix = 0;
        if (!end[t].empty()) {
            fix++;
            ans.push_back(end[t]);
            end[t] = "";
        }
        board[i][j] = 0;
        fix += dfs(board, i - 1, j, t, ans);
        fix += dfs(board, i + 1, j, t, ans);
        fix += dfs(board, i, j - 1, t, ans);
        fix += dfs(board, i, j + 1, t, ans);
        pass[t] -= fix;
        board[i][j] = tmp;
        return fix;
    }
};

}   // namespace lxj

#endif